请编写程序创建一个有向图。有向图中包含n个顶点，编号为0至n-1。

输入格式:

输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。

输出格式:

按顶点编号递增顺序输出每个顶点引出的边，每个顶点占一行，若某顶点没有引出边，则不输出。每行表示一个顶点引出的所有边，格式为a:(a,b,w)……，表示有向边a->b的权值为w，a引出的多条边按编号b的递增序排列。

输入样例:

1
2
3
4
5
6
7
8
7 7
0 1 5
0 3 7
0 6 6
1 2 4
2 5 1
3 5 3
6 5 4结尾无空行

输出样例:

1
2
3
4
5
0:(0,1,5)(0,3,7)(0,6,6)
1:(1,2,4)
2:(2,5,1)
3:(3,5,3)
6:(6,5,4)结  尾无空行

思路

算法1 邻接表

这里的链表采用的是包含头节点的形式，方便插入。插入的时候有序的插入，方便输出。

算法2 vector

其实也是邻接表的思路，只不过每个节点的邻接点没有用链表存储，用的vector，输出的时候先排序。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
using namespace std;
const int maxn = 20000+5;
typedef struct ENode *Edge;
struct ENode
{
    int idx;
    int w;
    Edge nextEdge;
};
struct VNode
{
    Edge firstEdge;
}nodes[maxn];

void print(int idx)
{
    if(nodes[idx].firstEdge->nextEdge==NULL) return ;

    printf("%d:",idx);
    Edge edge=nodes[idx].firstEdge->nextEdge;
    while(edge)
    {
        printf("(%d,%d,%d)",idx,edge->idx,edge->w);
        edge=edge->nextEdge;
    }
    puts("");
}
//在单链表的有序插入 把edge 插入到 nodes[idx].firstEdge所指向的链表里（以升序的形式） 
void insert(int idx,Edge edge)
{
    Edge tmp=nodes[idx].firstEdge;

    int curridx=edge->idx;
    while(tmp->nextEdge&&tmp->nextEdge->idx<curridx) tmp=tmp->nextEdge;//找到按照升序排列该插入的位置
    edge->nextEdge=tmp->nextEdge;
    tmp->nextEdge=edge;
}
int main()
{
    //init 
    for(int i=0;i<maxn;++i)
    {
        Edge edge=(Edge)malloc(sizeof(Edge));
        edge->nextEdge=NULL;
        nodes[i].firstEdge=edge;
    }
    
    int n,e;
    cin>>n>>e;
    while(e--)
    {
        int a,b,w;
        cin>>a>>b>>w;

        Edge edge=(Edge)malloc(sizeof(Edge));
        edge->idx=b,edge->w=w;
        edge->nextEdge=NULL;
        
        insert(a,edge);
    }
    for(int i=0;i<n;++i) print(i);
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 20000+5;
struct Node
{
    int idx;
    int w;
};
vector<Node> nodes[maxn];
void print(int idx)
{
    if(nodes[idx].size()==0) return ;
    printf("%d:",idx);

    sort(nodes[idx].begin(),nodes[idx].end(),[=](Node n1,Node n2){
        return n1.idx<n2.idx;
    });
    for(auto &node:nodes[idx]) printf("(%d,%d,%d)",idx,node.idx,node.w);
    puts("");
}
int main()
{
    int n,e;
    cin>>n>>e;
    while(e--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        Node node;
        node.idx=b,node.w=w;
        nodes[a].push_back(node);
    }

    for(int i=0;i<n;++i) print(i);
}